/*
 * @lc app=leetcode.cn id=39 lang=javascript
 *
 * [39] 组合总和
 */

// @lc code=start
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
// var combinationSum = function (candidates, target) {
//   let res = [],
//     length = candidates.length
//   const dps = (target, resItem, i) => {
//     if (target == 0) {
//       res.push(resItem)
//       return
//     }
//     if (i == length) return

//     dps(target, resItem, i + 1)

//     if (target - candidates[i] >= 0) {
//       dps(target - candidates[i], [...resItem, candidates[i]], i)
//     }
//   }

//   dps(target, [], 0)

//   return res
// }
var combinationSum = function (candidates, target) {
  let n = candidates.length
  let res = []
  let targetArr = []
  candidates = candidates.sort((a, b) => a - b)
  let backtrack = (targetArr, target, start) => {
    if (target == 0) {
      res.push(targetArr)
      return
    }
    for (let i = start; i < n; i++) {
      if (target < candidates[i]) break
      backtrack([...targetArr, candidates[i]], target - candidates[i], i)
    }
  }
  backtrack(targetArr, target, 0)
  return res
}

// @lc code=end
